/**
 * 两个条件：
 * 1. 后缀是s
 * 2. 数位不超过limit
 * 
 * 因为全是过滤条件，所以不用其他状态，直接设D[20]即可
 * 另外注意如果长度没有达到s.length()，直接返回0即可，无需进入搜索
 */
using llt = long long;
string * pS;
int N;
int Limit;
vector<int> G;
// 均是过滤条件，可以不用额外的状态
llt D[20];
llt dfs(int pos, bool lead, bool limit){
    if(-1 == pos) {
        return 1;
    }
    if(not lead and not limit and -1 != D[pos]) {
        return D[pos];
    }
    int last = limit ? G[pos] : 9;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(i > Limit) continue;
        if(pos < N and i != (*pS)[N - 1 - pos] - '0') continue;
        ans += dfs(pos - 1, lead&&0==i, limit&&last==i);
    }
    if(not lead and not limit){
        D[pos] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    if(G.size() < N) return 0;
    return dfs(G.size()-1, true, true);
}

class Solution {
public:
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        memset(D, -1, sizeof(D));
        N = (pS = &s)->length();        
        Limit = limit;
        return digitDP(finish) - digitDP(start - 1);     
    }
};